import copy

class Solution(object):
    def combine(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: List[List[int]]
        """
        ret = []
        acc = []
        def find(begin):
            if len(acc)==k:
                ret.append(copy.copy(acc))
                return
            
            if n+1-begin<k-len(acc):
                return

            for i in range(begin, n+1):
                acc.append(i)
                find(i+1)
                acc.pop()
        
        find(1)
        return ret

print(Solution().combine(20,16))